package com.lx.algorithm.code;

import java.util.Random;

/**
 * Description:
 * Copyright:   Copyright (c)2019
 * Company:     zefu
 *
 * @author: 张李鑫
 * @version: 1.0
 * Create at:   2021-12-30 10:21:49
 * <p>
 * Modification History:
 * Date         Author      Version     Description
 * ------------------------------------------------------------------
 * 2021-12-30     张李鑫                     1.0         1.0 Version
 */
public class Code04 {
    /**
     * 有一些排成一行的正方形。每个正方形已经被染成红色或者绿色。现在可以选择任意一个正方形然后用这两种颜色的任意一种进行染色,这个正方形的颜色将 会被覆盖。
     * 目标是在完成染色之后,每个红色R都比每个绿色G距离最左侧近。 返回最少需要涂染几个正方形。
     * 如样例所示: s = RGRGR 我们涂染之后变成RRRGG满足要求了,涂染的个数为2,没有比这个更好的涂染方案。
     */
    public static int colorLeftRight(String str) {
        int r = 0;
        int res = Integer.MAX_VALUE;
        char[] chars = str.toCharArray();

        for (int i = 0; i < chars.length; i++) {
            //统计其中一个字母出现了几次
            if (chars[i] == 'R') r++;
        }
        int gAll = 0;
        //比较边界值的时候 改几个字母
        res = Math.min(r, str.length() - r);
        for (int i = 0; i < chars.length; i++) {
            //这里变量无效 只是为了满足语法 这里统计左边有几个g 有的话g++ 没有的话r--
            int temp = chars[i] == 'G' ? gAll++ : r--;
            res = Math.min(r + gAll, res);
        }
        return res;
    }

    public static int minPaint(String s) {
        if (s == null || s.length() < 2) {
            return 0;
        }
        char[] str = s.toCharArray();
        int N = str.length;
        int rAll = 0;
        for (int i = 0; i < N; i++) {
            rAll += str[i] == 'R' ? 1 : 0;
        }
        int ans = rAll; // 如果数组所有的范围，都是右侧范围，都变成G
        int left = 0;
        for (int i = 0; i < N - 1; i++) { // 0..i 左侧 n-1..N-1
            left += str[i] == 'G' ? 1 : 0;
            rAll -= str[i] == 'R' ? 1 : 0;
            ans = Math.min(ans, left + rAll);
        }
        // 0...N-1 左全部 右无
        ans = Math.min(ans, left + (str[N - 1] == 'G' ? 1 : 0));
        return ans;
    }


    public static void main(String[] args) {
        Random random = new Random();

        for (int i2 = 0; i2 < 100; i2++) {
            StringBuilder stringBuilder = new StringBuilder();
            for (int i = 0; i < 1000; i++) {
                if (random.nextInt(100) % 2 == 0) {
                    stringBuilder.append("G");
                } else {
                    stringBuilder.append("R");
                }
            }
            String s = stringBuilder.toString();
            if (minPaint(s) != colorLeftRight(s)) {
                System.out.println("fuck");
            }
        }

    }
}
